\documentclass[10pt,twocolumn]{article}
\usepackage{graphicx, balance}

\topmargin -5mm
\textheight 225mm

\title{\bf Waste Truck Routing and Scheduling in Los Ba\~{n}os Laguna 
Using Vehicle Routing Heuristics}
\author{Carlo Luis M. Bation\\
 \small2008-24926\\ 
\small CMSC 190\\ 
 \small University of the 
  Philippines Los Ba\~{n}os}
\date{\small August 2011} % or \date{\today}

\begin{document}
\maketitle

\section{Introduction}


\subsection{Significance of the Study}
The study of waste management involves many fields. One of the main aspects of waste management is waste truck routing and scheduling. It greatly involves graph theory and route optimization on its background. We can say that each stop represents a node and the ways to each node represents the edges in graph theory. Solving the graph problem can lead to route optimization. This leads to the main theme of the study which is to improve scheduling and routing of waste truck in a given area using real world maps.
In the Philippines today, usually waste truck management is taken care by government offices and usually by the city of the mayor office. Most don’t have a system to schedule the routes of the waste trucks in their area. A routing system is needed in order to minimize cost, manpower and time. It minimizes cost by giving the shortest paths, the minimum way to traverse a group of clients or nodes and this will minimize the usage of gasoline. It also minimizes the possibility the truck to be damage because of the fact that the truck will traverse the minimum route and travel for a short time period. Manpower because we can come up with a solution of minimizing the number of trucks then if the number trucks to be used are minimized, the number of drivers and assistants will also be reduced. The use of time will also be minimized when we consider the weight and type of waste in each node as a parameter. When we know the estimated amount of waste per node the number of going back of the trucks to the depot will be reduce so cost and time here will be reduced.

In foreign countries there is a competition in waste collection. Many companies like SA Waste Holdings, Greenstar and WSN Environmental Solutions competes for customers. One of the factors that can be used as a main weapon on other companies is to have a better way of routing in order to traverse more nodes and to have minimum company expenses in the collection system.
The study also uses the real world maps. So that if a road or something was changed in the topography of the concerned area, the manager will just again run the system and it will produce new results of routes and schedules for the new map.

The map of Los Baños Laguna will be the first input in the system. This map has interesting routes and has many ways to traverse a given node or place meaning there are more than one way to go to a place. There is also one depot or dump site in the map so the problem will be simplified. The types of garbage in the map also vary. Because of the existence of hospitals in the map, the hospital waste will be included in the constraints of types of wastes. The map also includes the University of the Philippines Los Baños and inside the university there is a building called Physical Science building that produces toxic or chemical waste that is another type of waste. So, not just biodegradable and non-biodegradable types of wastes will be the constraint of the study. 

The focus of this paper is to develop software that can return near optimal routes and schedules for the waste truck to follow. The solutions will be based from vehicle routing heuristics like branch and bound and traveling salesman algorithms. The map of Los Baños Laguna will be the starting point of the study and other maps will be chosen as input to train the software to be generic and adapt in any kinds of map in the future.

\newpage
\subsection {Review of Related Literature}
Waste truck routing and scheduling can be solve using vehicle routing heuristics and other related concepts such the Traveling Problem. Heuristics are those methods that can be program in polynomial time and give results that are near to the optimal solution to the problem. Optimal solution can be achieved in exponential time, meaning as the number of input increases the amount of time also increases exponentially. Heuristics were developed in order to have an acceptable solution to a problem. It runs in polynomial time, meaning as the number of input increases the amount of time only increases linearly. In this part of the paper related literature about waste truck routing and scheduling in terms of combinatorial optimization will be presented.

The first is the Traveling Salesman Problem (TSP). It is based from the 1857 game called Icosian Game invented by Sir William R. Hamilton (J. Dalgety, 2009). The rule of the game is to visit 20 connected points with going to a point only once. We can relate traveling salesman to our problem by making the number of trucks equal to one. It means that the single truck will traverse all nodes or customers.

Branch and Bound algorithm can give a near optimal solution to TSP. The idea of branch and bound algorithm is that you will make a tree.  Find the row minimum of a given matrix of constraints then it will be the starting node of the tree. After finding the row minimum detect the indexes of the matrix that are involve in the row minimum Then compute the different sub tours of the remaining indexes of the matrix and again add the nodes to the parent and repeat the process until an stopping criteria is detected.  Branch and Bound algorithm was first presented by A.H. Land and A.G. Doig in their book.  The book also contains other combinatorial problems.

Many papers were publish and presentations were made regarding to the solution of TSP using the Branch and Bound Algorithm.  The concept of parallelization was also introduced to make the computation of nodes of the tree in the algorithm (S. Tschoeke and et al, 1995). This is done by assigning different task to each of the processors and because of this the result generation will be fast as like doing the computation in a sequential process with few data. 

A presentation made by Busby, Dodge, Fleming and Negrusa about Backtracking and Branch and Bound algorithm tells how the concept of backtracking helps to know the solution to the TSP in a faster way by implementing some methods related to backtracking. Remember that in Branch and Bound algorithm sometimes if the cost of the current child node is greater than the cost of the previous child nodes then it is needed to go back one higher level in order to come with another better solution and concepts of backtracking can help to find a better path. This is how the combination of backtracking and branch and bound algorithm works: (1) Branch and bound will create the tree of possible paths, (2) as it creates the tree a pointer will check if the current node has the lowest cost (3) then if not a backtracking algorithm will be used and the pointer to the current node will go to another node which have the lowest cost until near optimal path or a stopping criteria is found.

 An implementation of the said algorithm written in a programming language called java was made by Pawel Kalczynski in 2005.  Pawel made a package of classes in java based from the processes involved in the algorithm and in TSP. Pawel based his package in the Branch and Bound Algorithm made by Balas(1985).

As what we can see solving TSP using Branch and Bound Algorithm requires too much computing power and takes a lot of time. So we need some other methods that can solve TSP in a “serial” way or a simpler way. The paper of Christian Nilsson presents many different heuristics about TSP (2003). One of the methods that were presented was the nearest neighbour algorithm. The idea of this method is to find the nearest accessible node then go to it if it is not yet visited. In waste truck problem with the number of trucks equal to one the starting point is the depot or the garage of the truck and from the depot it will go to the nearest area assigned to it.

The next graph combinatorial problem related to the waste truck routing and scheduling is the vehicle routing problem (VRP). Given number of customers with each having certain demands (time and cost), each customer have distances on each other and each have weights (garbage in terms of waste collection). The goal of the VRP is to (1) minimize the number of vehicles to be use or to optimally use the existing number of vehicles (2) to satisfy the customers by getting the requirements on time and (3) to have a near optimal path to traverse all the customers(Garn, 2003).

Vehicle routing problem with time windows (VRPTW) is a type of VRP which added time as a constraint. The idea is that each node or customer has “starting time” and “end time”. The “starting time” is the earliest time the vehicle should arrive to the node and the “ending time” is the latest time the vehicle should arrive to the node.  Solomon on his paper on 1987 lists some heuristics on how to come up with a solution to the VRPTW. One of the heuristics that was presented on the paper is the time oriented nearest neighbour algorithm. The algorithm was similar to the TSP’s nearest neighbour algorithm the VRP version just added the number of vehicles and the time windows as additional constraints. Another heuristic that was presented by Solomon is the insertion heuristic. The goal of the heuristic is to insert a new node that is not yet in the current partial path. The insertion of the new node can be in any part of the partial path and the resulting partial path of the insertion should be feasible. 

In terms of waste truck routing not only time windows can be added as a constraint but also the lunch break of the drivers also needs to be consider (Byung-In and et al., 2005).  Extension of Solomon’s insertion algorithm was made so that a better time window handling will be done and to have an optimal lunch break for the drivers.

Another constraint that can be added to the problem is the number of available vehicles that already existed (Hoong and et al., 2003). The problem here is that what if the number of vehicles available where not yet sufficient in order to have the optimal path for waste collection so some customers will be not served. Holding list is used to store customers that were not served in the resulting path. Maximization of customers into the vehicles was made so that all customers will be served. Tabu search was used to insert customers in a vehicle schedule. Tabu search is an enhanced version of local search. It uses data structures to store all visited candidate solutions to avoid repetition in searching.

Evolutionary methods such as genetic algorithm and coevolutionary genetic algorithm approach can be used in solving VRP (Penousal, 2002). These methods can come up with better solutions than normal heuristics. Both algorithms came from the concept of genetics in science mainly the theory of evolution of Charles Darwin. The algorithm can be simply describe in this steps: (1) generate possible solutions (2) evolve this solutions to new set of solutions (3) loop until a stopping criteria is found.The solutions will evolve as the given constraints changes. The coevolutionary genetic algorithm add some heuristics, like nearest neighbour algorithm, to generate some of the possible solutions while the simple genetic algorithm uses random possible solutions at the starting phase of the genetic algorithm. So the result of the coevolutionary genetic algorithm is nearer to the optimal solution than the result of the simple genetic algorithm.

In this study we will use the data generated by Open Street Map (http://www.openstreetmap.org/) an open source online mapping system. In Open Street Map you can convert a given map into xml and download it. This xml file have attributes like “lat” (latitude) and “long” (longitude) that can be used into knowing the position of a place in the map this is from. In the Philippines there are two websites that are using Open Street Map as their mapping service for their users. Those are Ortigas Online and Red Cross Rizal Chapter. The Wikipedia page(http://wiki.openstreetmap.org/)  of Open Street Map is the source for this data.
Traveling Salesman Problem algorithms are essential for path finding and can help solving the problem with the number of trucks is equal to one. Vehicle Routing Problem with Time Windows algorithms are essential for routing with capacity and time as main constraints. The basics and some applications of openstreetmap is essential in order to have a real world nodes represented by the places in the given map. These concepts can help me accomplish my objectives in this study.

\subsection {Objectives of the Study}

The main objective of this study is to make software that produces near optimal routes and schedules for waste trucks given an input map from openstreetmap.org.
\begin{itemize}

\item To solve the problem using vehicle routing problem heuristics.

\item To make a graphical user interface from the map that can accept inputs from user. Examples of inputs are name of the area, weight of garbage in an area and time window for that area.

\item To produce routes lines in the given map and schedules as an output. Routes lines are lines that connect one area from another area based from the resulting path. An assignment colour for a truck will be given to visualize the route of a truck in the map. For example for truck A colour yellow will be given.

\item To extend the constraints into heterogeneous trucks. Meaning that a truck can have different capacities and specs.

\item To start to the map of Los Baños Laguna as the first input to the software.

\end{itemize}

\balance
\subsection{Date and Place of  Study}

The study will be done at the Institute of Computer Science, College of Art and Science University of the Philippines Los Baños Laguna from October 2011 to January 2012.
	

{\small \begin{flushleft}
\begin{thebibliography}{}

\bibitem[1]{1} N.D Waste companies. In Wikipedia. Retrieved October 15, 2010, Available from: http://en.wikipedia.org/wiki/Category: \\ Waste\_companies 
\bibitem[2]{2}DALGETY, J. (2009).The Icosian Game. [online], Available from: \\  http://www.puzzlemuseum.com/month \\ /picm02/200207icosian.htm 
\bibitem[3]{3}LAND, A. H.and A. G. DOIG (1960). An automatic method of solving discrete programming 
problems. Econometrica 28 (3): pp. 497-520

\bibitem[4]{4}TSCHOEKE, S., R. LUELING and B. MONIEN.(1995) .Solving the Traveling Salesman 
Problem with a Distributed Branch-and-Bound Algorithm on a 1024 Processor 
Network, in Journal of Parallel Processing Symposium.pp. 182-189 
\bibitem[5]{5}BUSBY and et al.,(2009). Backtracking and Branch and Bound Algorithm

\bibitem[6]{6}KALCZYNSKI P., (2005) A Java Implementation of the Branch and Bound Algorithm: the 
Asymetric Traveling Salesman Problem, in Journal of Object Technology, 4(1) pp.    
155-163.
\bibitem[7]{7}BALAS, E. and P. TOTH, (1985) Branch and Bound Methods, in E.L. Lawler, J.K. Lenstra, 
A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem: A 
Guided Tour of Combinatorial Optimization, Wiley, New York, pp.361 - 401.

\bibitem[8]{8}NILSSON, C., (2003) Heuristics for the Traveling Salesman Problem. A Report for 
Theoretical Computer Science. 

\bibitem[9]{9}GARN W. (2007) Vehicle Routing Problem Algorithm [online], Available from: 
 http://osiris.tuwien.ac.at/\textasciitilde{}wgarn/VehicleRouting/ \\  vehicle\_routing.html

\bibitem[10]{10}SOLOMON M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with 
Time Window Constraints, in Journal of  Operations Research 35 pp.254-265


\bibitem[11]{11}BYUNG-IN, K., K. SEONGBAE and S. SURYA (2005) Waste collection vehicle routing 
Problem with Time Windows

\bibitem[12]{12}HOONG CHUIN L., S. MELVYN AND M.T. KWONG (2003) Vehicle Routing Problem 
with Time Windows and a Limited Number of Vehicles

\bibitem[13]{13}PENOUSAL M, T. JORGE, P. FRANCISCO, C ERNESTO. (2002), Vehicle Routing 
Problem: Doing it the Evolutionary Way, Genetic and Evolutionary Computation 
Conference, GECCO-02, New York, USA

\end{thebibliography}

\end{flushleft}}


\end{document}

